package com.zklh.leetcode.top100;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 二维矩阵中最大面积算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/11/10
 */
public class SolutionLCR039Plus {

    /**
     * 合并矩形, 优先合并最大的, 其余的尽量合并即可
     * @param grid
     * @return 返回各个矩形的位置, 格式是 左上角坐标x,y = (int[0],int[1]), 右下角坐标 int[2], int[3]
     */
    public int[] largestRectangleArea(int[][] grid) {
        int[] heights = new int[grid[0].length];
        int maxArea = 0;
        int[] maxAreaPosition = new int[4];
        // 每行都可以作为底边 求最大矩形
        for (int row = 0; row < grid.length; row++) {
            /* 得到当前层的最大高度 */
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == 0) {
                    heights[col] = 0;
                } else {
                    heights[col] = heights[col] + 1;
                }
            }

            /* 判断当前层最大的面积 */
            int[] rectangle = largestRectangleArea(heights);
            int currentArea = (rectangle[1] - rectangle[0] + 1) * rectangle[2];
            if (maxArea < currentArea) {
                maxArea = currentArea;
                maxAreaPosition[0] = row - rectangle[2] + 1;
                maxAreaPosition[1] = rectangle[0];
                maxAreaPosition[2] = row;
                maxAreaPosition[3] = rectangle[1];
            }
        }
        return maxAreaPosition;
    }


    /**
     * 获取指定直方图最大的面积, 返回直方图面积的最左和最右索引以及 高度
     * @param heights
     * @return
     */
    private int[] largestRectangleArea(int[] heights) {
        Deque<Integer> deque = new LinkedList<>();
        int[] left = new int[heights.length];
        int[] right = new int[heights.length];
        for (int i = 0; i < heights.length; i++) {
            while (!deque.isEmpty() && heights[deque.peek()] >= heights[i]) {
                right[deque.peek()] = i;
                deque.poll();
            }
            left[i] = deque.isEmpty() ? -1 : deque.peek();
            deque.push(i);
        }
        while (!deque.isEmpty()) {
            right[deque.poll()] = heights.length;
        }

        int maxArea = 0;
        int[] result = new int[3];
        for (int i = 0; i < heights.length; i++) {
            int currentArea = heights[i] * (right[i] - left[i] - 1);
            if(currentArea > maxArea) {
                maxArea = currentArea;
                result[0] = left[i] + 1;
                result[1] = right[i] - 1;
                result[2] = heights[i];
            }
        }
        return result;
    }

    public static void main(String[] args) {
        SolutionLCR039Plus solutionLCR039Plus = new SolutionLCR039Plus();
        int[][] grid = {
                {1, 0, 1, 1, 1},
                {1, 1, 1, 0, 1},
                {0, 1, 1, 1, 0},
                {1, 1, 1, 1, 0},
                {0, 1, 1, 1, 1}};
        System.out.println(Arrays.toString(solutionLCR039Plus.largestRectangleArea(grid)));
    }
}